/*
 * SparseArray.h
 *
 *  Created on: 2012-10-30
 *      Author: yangentao@gmail.com
 */

/*
 * SparseArray.h
 *
 *  Created on: 2012-10-30
 *      Author: yangentao@gmail.com
 */

#pragma once;
#include "baseutil.h"
namespace yet{
template<typename VT>
class ValueWrap {
public:
	VT val;
	bool del;
public:
	ValueWrap() {
		val = VT();
		del = false;
	}
	ValueWrap(const VT& value) {
		val = value;
		del = false;
	}
};

template<typename T>
class SparseArray {
private:

	typedef ValueWrap<T> ValueType;
private:
	AutoBuffer<int> mKeys;
	AutoBuffer<ValueType> mValues;
	int mSize;
	bool mGarbage;
private:
	int idealIntArraySize(int cap) {
		return cap >= 8 ? cap + cap : 10;
	}

public:
	virtual ~SparseArray() {

	}
	SparseArray() {
		init(10);
	}

	SparseArray(int initialCapacity) {
		init(initialCapacity);
	}
	void init(int capcity_) {
		int capcity = idealIntArraySize(capcity_);
		mKeys.init(capcity);
		mValues.init(capcity);
		mSize = 0;
		mGarbage = false;
	}
public:
	T get(int key) {
		return get(key, T());
	}
	T get(int key, T valueIfKeyNotFound) {
		int i = binarySearch(mKeys.buffer, 0, mSize, key);

		if (i < 0 || mValues.buffer[i].del) {
			return valueIfKeyNotFound;
		} else {
			return mValues.buffer[i].val;
		}
	}

	void remove(int key) {
		int i = binarySearch(mKeys.buffer, 0, mSize, key);

		if (i >= 0) {
			if (!mValues.buffer[i].del) {
				mValues.buffer[i].del = true;
				mGarbage = true;
			}
		}
	}
	void gc() {
		int n = mSize;
		int o = 0;
		int* keys = mKeys.buffer;
		ValueType* values = mValues.buffer;
		for (int i = 0; i < n; i++) {
			if (!values[i].del) {
				if (i != o) {
					keys[o] = keys[i];
					values[o] = values[i];
				}
				o++;
			}
		}
		mGarbage = false;
		mSize = o;
	}

	void put(int key, T value) {
		int i = binarySearch(mKeys.buffer, 0, mSize, key);

		if (i >= 0) {
			mValues.buffer[i].val = value;
			mValues.buffer[i].del = false;
		} else {
			i = ~i;

			if (i < mSize && mValues.buffer[i].del) {
				mKeys[i] = key;
				mValues.buffer[i].val = value;
				mValues.buffer[i].del = false;
				return;
			}

			if (mGarbage && mSize >= mKeys.length) {
				gc();

				// Search again because indices may have changed.
				i = ~binarySearch(mKeys.buffer, 0, mSize, key);
			}

			if (mSize >= mKeys.length) {
				int n = idealIntArraySize(mSize + 1);
				AutoBuffer<int> nKeys(n);
				AutoBuffer<ValueType> nvalues(n);
				ArrayMove(nKeys.buffer, mKeys.buffer, mKeys.length);
				ArrayMove(nvalues.buffer, mValues.buffer, mValues.length);
				mKeys.grab(nKeys);
				mValues.grab(nvalues);
			}

			if (mSize - i != 0) {
				ArrayMove(mKeys.buffer, i + 1, mKeys.buffer, i, mSize - i);
				ArrayMove(mValues.buffer, i + 1, mValues.buffer, i, mSize - i);
			}

			mKeys.buffer[i] = key;
			mValues.buffer[i].val = value;
			mValues.buffer[i].del = false;
			mSize++;
		}
	}

	int size() {
		if (mGarbage) {
			gc();
		}
		return mSize;
	}
	int length() {
		return size();
	}
	bool isEmpty(){
		return size() ==0;
	}

	int keyAt(int index) {
		if (mGarbage) {
			gc();
		}
		return mKeys[index];
	}

	T valueAt(int index) {
		if (mGarbage) {
			gc();
		}

		return mValues[index].val;
	}

	void setValueAt(int index, T value) {
		if (mGarbage) {
			gc();
		}

		mValues.buffer[index].value = value;
		mValues.buffer[index].del = false;
	}

	int indexOfKey(int key) {
		if (mGarbage) {
			gc();
		}
		return binarySearch(mKeys.buffer, 0, mSize, key);
	}

	int indexOfValue(T value) {
		if (mGarbage) {
			gc();
		}
		for (int i = 0; i < mSize; i++) {
			if (mValues[i] == value) {
				return i;
			}
		}
		return -1;
	}

	void clear() {
		mValues.release();
		mKeys.release();
		mSize = 0;
		mGarbage = false;
	}

	void append(int key, T value) {
		if (mSize != 0 && key <= mKeys[mSize - 1]) {
			put(key, value);
			return;
		}

		if (mGarbage && mSize >= mKeys.length) {
			gc();
		}

		int pos = mSize;
		if (pos >= mKeys.length) {
			int n = idealIntArraySize(pos + 1);

			AutoBuffer<int> nkeys(n);
			AutoBuffer<ValueType> nvalues(n);

			ArrayMove(nkeys.buffer, mKeys.buffer, mKeys.length);
			ArrayMove(nvalues.buffer, mValues.buffer, mValues.length);

			mKeys.grab(nkeys);
			mValues.grab(nvalues);
		}

		mKeys[pos] = key;
		mValues[pos].val = value;
		mValues[pos].del = false;

		mSize = pos + 1;
	}
//
private:
	static int binarySearch(int* a, int start, int len, int key) {
		int high = start + len, low = start - 1, guess;

		while (high - low > 1) {
			guess = (high + low) / 2;

			if (a[guess] < key)
				low = guess;
			else
				high = guess;
		}

		if (high == start + len)
			return ~(start + len);
		else if (a[high] == key)
			return high;
		else
			return ~high;
	}

};

}
